package sort.leetcode.medium;

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.concurrent.ThreadLocalRandom;

/**
 * @author Stark
 * @description 数组中的第K个最大元素
 * @date 2022/4/17 20:54
 **/
public class Num215_FindKthLargest {
    int choice = 1;
    public static final ThreadLocalRandom RANDOM = ThreadLocalRandom.current();
    public int findKthLargest(int[] nums, int k) {
        if(choice == 1){
            //方法一
            //使用排序对数组进行排序
            //时间复杂度：O(nlogn)
            Arrays.sort(nums);
            return nums[nums.length - k];
        }
        if(choice == 2){
            //方法二
            // 使用小堆,最后返回堆顶元素即可
            //时间复杂度:O(nlogm)
            Queue<Integer> queue = new PriorityQueue<>(k);
            for (int i = 0; i < nums.length; i++) {
                if(i < k){
                    queue.offer(nums[i]);
                }else{
                    if(nums[i] > queue.peek()){
                        queue.poll();
                        queue.offer(nums[i]);
                    }
                }
            }
            return queue.peek();
        }
        if(choice == 3){
            //方法三
            //使用快排的分区函数,根据索引选择区间,直到找到第k大的数
            //时间复杂度:O(n)
            return find(nums,0,nums.length - 1,k);
        }
        return 0;
    }

    private int find(int[] nums, int left, int right,int k) {
        if(left >= right)
            return nums[left];
        //分区函数,左区间的值都小于arr[mid]
        //右区间的值都大于arr[mid]
        int mid = partition(nums,left,right);
        //计算该值是数组中第几大的元素！！！
        int findK = nums.length - mid;
        //注意,这里比较的是第几大的数而选择的区间
        if(findK < k)
            return find(nums, left, mid - 1, k);
        else if(findK == k)
            return nums[mid];
        else
            return find(nums, mid + 1, right, k);
    }

    //挖坑法
    private int partition(int[] nums, int left, int right) {
        int randomIndex = RANDOM.nextInt(left,right);
        swap(nums,left,randomIndex);
        int pivot = nums[left];
        int start = left;
        int end = right;
        while(start < end){
            while(start < end && nums[end] >= pivot)
                end--;
            nums[start] = nums[end];
            while(start < end && nums[start] <= pivot)
                start++;
            nums[end] = nums[start];
        }
        nums[start] = pivot;
        return start;
    }
    //单路快排
    public int partition1(int[] nums,int left,int right){
        int randomIndex = RANDOM.nextInt(left,right);
        swap(nums,left,randomIndex);
        int v = nums[left];
        int i = left + 1;
        int j = left;
        while(i <= right){
            //只需要交换小于基准值的数
            if(nums[i] < v){
                swap(nums,j + 1,i);
                j++;
            }
            i++;
        }
        swap(nums,j,left);
        return j;
    }

    //二路快排
    private int partition2(int[] nums,int left,int right){
        int randomIndex = RANDOM.nextInt(left,right);
        swap(nums,left,randomIndex);
        int v = nums[left];
        int i = left + 1;
        int j = right;
        while(true){
            while(i <= j && nums[i] < v)
                i++;
            while(i <= j && nums[j] > v)
                j--;
            if(i < j)
                swap(nums,i++,j--);
            else
                break;
        }
        swap(nums,left,j);
        return j;
    }

    //三路快排
    public void quickSort(int[] nums,int left,int right){
        if(left >= right)
            return;
        int randomIndex = RANDOM.nextInt(left,right);
        swap(nums,left,randomIndex);
        int v = nums[left];
        int lt = left;
        int gt = right + 1;
        int i = left + 1;
        while(i < gt){
            if(nums[i] < v){
                swap(nums,lt + 1,i);
                lt++;
                i++;
            }else if(nums[i] == v){
                i++;
            }else{
                swap(nums,gt - 1,i);
                gt--;
            }
        }
        swap(nums,lt,left);
        quickSort(nums,left,lt - 1);
        quickSort(nums,gt,right);
    }

    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}
